import java.util.Stack;

public class Sort {
    //直接插入排序
    /*
    时间复杂度：最坏O(N^2)
              最好O(N) 数组越有序，速度越快
    空间复杂度：O(1)
    稳定性：   稳定排序
    */
    public static void insertSort(int[] arr){
        for (int i = 1; i <arr.length ; i++) {
            int temp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    //希尔排序，直接插入排序的优化
    /*
    时间复杂度：O(N^1.3-N^1.5)
    空间复杂度：O(1)
    稳定性：   不稳定排序
    */
    public static void shellSort(int[] arr){
        int gap=arr.length;
        while(gap!=1){
            gap/=2;
            shell(arr,gap);
        }
    }
    private static void shell(int[] arr,int gap){
        for (int i = gap; i <arr.length ; i+=gap) {
            int temp=arr[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=temp;

        }
    }
    //选择排序（有两种）
    /*
    时间复杂度：O(N^2)
    空间复杂度：O(1)
    稳定性：   不稳定排序
    */
    public static void selectSort(int[] arr){
        for (int i = 0; i <arr.length ; i++) {
            int minIndex=i;
            for (int j = i+1; j < arr.length ; j++) {
                if(arr[minIndex]>arr[j]){
                    minIndex=j;
                }
            }
            swap(arr,i,minIndex);
        }
    }
    /*
    时间复杂度：O(N^2)
    空间复杂度：O(1)
    稳定性：  不稳定排序
    */
    public static void selectSortMaxMin(int[] arr){
        int left=0;
        int right=arr.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <=right ; i++) {
                if(arr[maxIndex]<arr[i]){
                    maxIndex=i;
                }
                if(arr[minIndex]>arr[i]){
                    minIndex=i;
                }
            }
            swap(arr,maxIndex,right);
            if(minIndex==right){
                minIndex=maxIndex;
            }
            swap(arr,minIndex,left);
            left++;
            right--;
        }
    }
    //堆排序
    /*
    时间复杂度：O(n log n)
    空间复杂度：O(1)
    稳定性：  不稳定排序
    */
    public static void heapSort(int[] arr) {
        createHeap(arr);
        int end=arr.length;
        while(end>0){
            swap(arr,0,end-1);
            siftDown(arr,0,end-1);
            end--;
        }
    }
    private static void createHeap(int[] arr){
        for (int parent =(arr.length-1-1)/2 ; parent >=0; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }
    private static  void siftDown(int[] arr,int parent,int usedSize){
        int child=2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize&&arr[child+1]>arr[child]){
                child++;
            }
            if(arr[child]>arr[parent]){
                swap(arr,parent,child);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    //冒泡排序（带优化
    /*
    时间复杂度：O(N^2)
             带优化的最好情况是O(N)
    空间复杂度：O(1   ）
    稳定性：   稳定的排序
    */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i <arr.length-1 ; i++) {
            boolean flag=false;
            for (int j = 0; j <arr.length-1-i ; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
            if(flag==false) break;
        }
    }
    //
    private static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    //快排
    /*
         1.找基准(找基准过程中将左右划分了)
         2.左边 划分完成
         3.右边 划分完成
     */
    /*
         时间复杂度：最坏的情况下是O(n),此时为单分支树
                  但是我们一般不这么说快排的时间复杂度
                  O(n* log n)
         空间复杂度：最坏情况下：O(n),此时为单分支树
                   一般：O(log n)
         稳定性：   不稳定的排序
     */
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }

    private static void quick(int[] arr,int left,int right){
        if(left>=right) return;
        //到达一定程度我们直接使用插入排序
        if(right-left+1==4){
            quickInsert(arr,left,right);
            return;
        }
        int mid=midThreeNum(arr,left,right);//三数找中
        swap(arr,left,mid);

        int par=partitionHole(arr,left,right);
        quick(arr,left,par-1);
        quick(arr,par+1,right);
    }
    //Hoare版本找基准
    private static int  partition(int[] arr,int left,int right){
        int start=left;
        int end=right;
        int temp=arr[start];
        while(start<end){
            while (start<end&&arr[end]>=temp)
                end--;
            while (start<end&&arr[start]<=temp)
                start++;
            swap(arr,end,start);
        }
        swap(arr,left,start);
        return start;
    }
    //挖坑法版本找基准
    private  static int partitionHole(int[] arr,int left,int right){
        int start=left;
        int end=right;
        int temp=arr[start];
        while(start<end){
            while (start<end&&arr[end]>=temp){
                end--;
            }
            arr[start]=arr[end];
            while (start<end&&arr[start]<=temp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=temp;
        return start;
    }
    //对快排进行优化  1.三数找中值，因为有时候选左边的数当作基准，容易造成但分支数，三数找中间可以避免这种情况
    private static int midThreeNum(int[] arr,int left,int right){
        int mid=(left+right)/2;
        if(arr[left]<arr[right]){
            if(arr[mid]<arr[left])
                return  left;
            else if(arr[mid]>arr[right])
                return right;
            else{
                return mid;
            }
        }
        // arr[right]<=arr[left]
        else{
            if(arr[mid]<arr[right])
                return  right;
            else if(arr[mid]>arr[left])
                return left;
            else{
                return mid;
            }
        }
    }
    //2  数组是越排越有序，当排到一定程度，我们可以用，插入排序
    private static void quickInsert(int[] arr,int left,int right){
        for (int i = left+1; i <=right ; i++) {
            int temp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    //非递归实现快排
    public static void quickSortNoRecurrence(int[] arr){
        quickNoRecurrence(arr,0,arr.length-1);
    }
    private static  void quickNoRecurrence(int[] arr,int start,int end){
        Stack<Integer> stack=new Stack<>();
        int left=start;
        int right=end;
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()){
             right=stack.pop();
             left=stack.pop();
             int par=partitionHole(arr,left,right);
             if(par-1-left+1>=2)
             {
                 stack.push(left);
                 stack.push(par-1);
             }
             if(right-par-1+1>=2){
                 stack.push(par+1);
                 stack.push(right);
             }
        }
    }
    //归并排序 :先分解  再递归回来归并
    /*
    时间复杂度: O(n*log n)
    空间复杂度：O(n)
    稳定性：稳定的排序
     */
    public static void mergeSort(int[] arr){
        merge(arr,0,arr.length-1);
    }
    private static void merge(int[] arr,int left,int right){
        if(left==right) return ;
        int mid=(left+right)/2;
        //分解
        merge(arr,left,mid);
        merge(arr,mid+1,right);
        //归并
        combine(arr,left,mid,right);

    }
    private static  void combine(int[] arr,int left,int mid,int right){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int[] tmpArr=new int[right-left+1];
        int k=0;
        while (s1<=e1&&s2<=e2){
            if(arr[s1]<arr[s2]){
                tmpArr[k++]=arr[s1++];
            }else{
                tmpArr[k++]=arr[s2++];
            }
        }
        while (s1<=e1){
            tmpArr[k++]=arr[s1++];
        }
        while (s2<=e2){
            tmpArr[k++]=arr[s2++];
        }
        for (int i = 0; i <tmpArr.length ; i++) {
            arr[i+left]=tmpArr[i];
        }
    }
    //非递归完成二路归并算法
    public static  void mergeSortNoRecurrence(int[] arr){
        int gap=1;
        while(gap<arr.length){
            for (int i = 0; i <arr.length ; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                //left不会超，但是mid 和 right 有可能会超
                if(mid>arr.length-1) mid=arr.length-1;
                if(right>arr.length-1) right=arr.length-1;
                combine(arr,left,mid,right);
            }
            gap*=2;
        }
    }
    //不用比较的排序算法
    /*
    1 . 计数算法:用计数器
    2 . 桶排序：一个一个的桶当作是范围，在桶里排好，在排在一起即可
    3 . 基数排序：每一个数都是十进制的数字，用0-9的队列数组去按各位排，按十位排，按千位排。。。。，每排一次就以某位有序，排完即可有序
     */
    //计数算法实现
    /*
       时间复杂度:O(MAX(范围,n))
       空间复杂度：O(范围)
       稳定性： 稳定性排序
     */
    public static void countSort(int[] arr){
        int min=arr[0];
        int max=arr[0];
        for (int i = 0; i <arr.length ; i++) {
            if(min>arr[i])
                min=arr[i];
            if(max<arr[i])
                max=arr[i];
        }
        int[] tempArr=new int[max-min+1];
        for (int i = 0; i <arr.length ; i++) {
            int index=arr[i]-min;
            tempArr[index]++;
        }
        int m=0;
        for (int i = 0; i <tempArr.length ; i++) {
            while (tempArr[i]!=0){
                arr[m++]=i+min;
                tempArr[i]--;
            }
        }
    }






























}
